package com.fps.webshop.question.question0100_0199;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

/**
 * 136. 只出现一次的数字
 * 
 * 给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
 * 
 * 说明：
 * 		你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
 * 
 * 示例 1:
 * 输入: [2,2,1]
 * 输出: 1
 * 
 * 示例 2:
 * 输入: [4,1,2,1,2]
 * 输出: 4
 */
public class Question136 {
	
	/**
	 * 第一次提交，先排序，再比较，但排序耗时比较大
	 * 
	 * 提交结果	执行用时	内存消耗	语言		提交时间				备注
	 * 通过		7 ms	38.8 MB	Java	2021/08/26 11:11
	 * 
	 * 执行用时：7 ms, 在所有 Java 提交中击败了24.89%的用户
	 * 内存消耗：38.8 MB, 在所有 Java 提交中击败了13.97%的用户
	 */
	public static int singleNumber(int[] nums) {
		if(nums.length==1) {
			return nums[0];
		}
		Arrays.sort(nums);
		for(int i = 0;i<nums.length;i++) {
			if(i==0) {
				if(nums[i]!=nums[i+1]) {
					return nums[i];
				}
			}else if(i==nums.length-1) {
				if(nums[i]!=nums[i-1]) {
					return nums[i];
				}
			}else {
				if(nums[i]!=nums[i-1]&&nums[i]!=nums[i+1]) {
					return nums[i];
				}
			}
		}
		return -1;
    }
	
	/**
	 * 第2次提交，代码稍微简化
	 * 
	 * 提交结果	执行用时	内存消耗	语言		提交时间				备注
	 * 通过		6 ms	38.8 MB	Java	2021/08/26 11:15
	 * 
	 * 执行用时：6 ms, 在所有 Java 提交中击败了29.48%的用户
	 * 内存消耗：38.8 MB, 在所有 Java 提交中击败了19.13%的用户
	 */
	public int singleNumber2(int[] nums) {
        if(nums.length==1) {
			return nums[0];
		}
		Arrays.sort(nums);
		for(int i = 0;i<nums.length-1;i++) {
			if(nums[i]!=nums[i+1]) {
				return nums[i];
			}else {
				i++;
			}
		}
		return nums[nums.length-1];
    }
	
	/**
	 * 第3次提交，尝试不排序，使用HashSet，但更慢了
	 * 
	 * 提交结果	执行用时	内存消耗	语言		提交时间				备注
	 * 通过		9 ms	38.9 MB	Java	2021/08/26 11:21
	 * 
	 * 执行用时：9 ms, 在所有 Java 提交中击败了19.94%的用户
	 * 内存消耗：38.9 MB, 在所有 Java 提交中击败了10.85%的用户
	 */
	public int singleNumber3(int[] nums) {
        if(nums.length==1) {
			return nums[0];
		}
        Set<Integer> aaa = new HashSet<>();
		for(int i = 0;i<nums.length;i++) {
			if(!aaa.add(nums[i])) {
				aaa.remove(nums[i]);
			}
		}
		for(Integer s :aaa) {
			return s;
		}
		return -1;
    }
	
	/**
	 * 第4次提交，参考网友，使用位运算
	 * 
	 * 提交结果	执行用时	内存消耗	语言		提交时间				备注
	 * 通过		3 ms	38.4 MB	Java	2021/08/26 11:24
	 * 
	 * 执行用时：3 ms, 在所有 Java 提交中击败了30.53%的用户
	 * 内存消耗：38.4 MB, 在所有 Java 提交中击败了80.81%的用户
	 */
	public int singleNumber4(int[] nums) {
        return Arrays.stream(nums).reduce((a,b)->a^b).getAsInt();
    }
	
	/**
	 * 第5次提交，官方解答，使用位运算
	 * 
	 * 提交结果	执行用时	内存消耗	语言		提交时间				备注
	 * 通过		1 ms	38.7 MB	Java	2021/08/26 11:26
	 * 
	 * 执行用时：1 ms, 在所有 Java 提交中击败了100.00%的用户
	 * 内存消耗：38.7 MB, 在所有 Java 提交中击败了39.59%的用户
	 */
	public int singleNumber5(int[] nums) {
        int single = 0;
        for (int num : nums) {
            single ^= num;
        }
        return single;
    }
	
	public static void main(String[] args) {
		int[] people = new int[] {3,5,3,4};
		System.out.print(singleNumber(people));
	}
}
